# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 4/50 使用最小花费爬楼梯
# leetcode第746题: https://leetcode.cn/problems/min-cost-climbing-stairs/description/

def minCostClimbingStairs(cost: list[int]) -> int:
    """我的答案"""
    n = len(cost)
    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]
    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

    return min(dp[n - 1], dp[n - 2])


def minCostClimbingStairs_std(cost: list[int]) -> int:
    """标准答案, 区别是dp[i]表示的内容不同, 在我的答案中, dp[i]表示的是在登上i级台阶后付费继续往上爬的代价.
    而在标准答案中dp[i]表示的是在登上第i级台阶但还没有付费时的代价"""
    n = len(cost)
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 0
    for i in range(2, n + 1):
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

    return dp[n]


if __name__ == '__main__':
    cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]  # 6
    print(minCostClimbingStairs(cost))
    cost1 = [10, 15, 20]  # 15
    print(minCostClimbingStairs(cost1))
